package org.algorithm.List;

import java.util.List;

public class Reverse {

    /**
     * 链表反转 双指针
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head)
    {
        ListNode current = head;
        ListNode prev =null;
        ListNode temp = head;

        while (current!=null)
        {
            temp = temp.next;
            current.next = prev;
            prev=current;
            current=temp;
        }

        return prev;
    }


    /**
     * 反转列表 递归
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head)
    {
        return reverse(null,head);
    }

    private ListNode reverse(ListNode prev,ListNode current)
    {
        if (current==null)
        {
            return prev;
        }

        ListNode temp = null;

        temp=current.next;
        current.next = prev;
//        prev=current;
//        current=temp;

        return reverse(current,temp);
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, null)));

        Reverse test = new Reverse();
        ListNode reverseList = test.reverseList2(listNode);
    }
}
